//
//  Tree.cpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/7/24.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#include "Tree.hpp"

// 初始化队列
void InitQueue(Queue &Q)
{
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->next = nullptr;
    Q.front = s;
    Q.rare = Q.front;
}

// 判断队空
bool isEmpty(Queue Q)
{
    return Q.rare == Q.front;
}

// 入队
bool EnQueue(Queue &Q, BiTNode *p)
{
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = p;
    s->next = nullptr;
    Q.rare->next = s;
    Q.rare = s;
    return true;
}

// 出队
bool DeQueue(Queue &Q, BiTNode *p)
{
    if (isEmpty(Q))
        return false;
    LNode *s = Q.front->next;
    if (s == Q.rare)
        Q.rare = Q.front;
    p = s->data;
    Q.front->next = s->next;
    free(s);
    return true;
}

// 访问树
void visit(BiTree T)
{
    printf("%d\n", T->value);
}
// *先序遍历*（递归）
void PreOrder(BiTree T)
{
    if (T != nullptr) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
// *中序遍历*（递归）
void MidOrder(BiTree T)
{
    if (T != nullptr) {
        MidOrder(T->lchild);
        visit(T);
        MidOrder(T->rchild);
    }
}
// *后序遍历*（递归）
void LastOrder(BiTree T)
{
    if (T != nullptr) {
        LastOrder(T->lchild);
        LastOrder(T->rchild);
        visit(T);
    }
}
// **树的深度**（递归）
int TreeDeep(BiTree T)
{
    if (T == nullptr) {
        return 0;
    } else {
        int l = TreeDeep(T->lchild);
        int r = TreeDeep(T->rchild);
        return l > r ? l + 1 : r + 1;
    }
}

// *层次遍历*
void LevelOrder(BiTree T)
{
    Queue Q;
    InitQueue(Q);
    EnQueue(Q, T);
    BiTNode *p = nullptr;
    while (!isEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != nullptr)
            EnQueue(Q, p->lchild);
        if (p->rchild != nullptr)
            EnQueue(Q, p->rchild);
    }
}

// *** 中序线索化 ***
void Tvisit(ThreadNode *q, ThreadNode *pre)
{
    if (q->lchild == nullptr){
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}

void InThread(ThreadTree &T, ThreadNode *pre)
{
    if (T != nullptr) {
        InThread(T->lchild, pre);
        Tvisit(T, pre);
        InThread(T->rchild, pre);
    }
}

void CreateInThread(ThreadTree &T)
{
    ThreadNode *pre = nullptr;
    if (T != nullptr) {
        InThread(T, pre);
        if (pre->rchild == nullptr) {
            pre->rtag = 1;
        }
    }
}

// *** 先序线索化 ***
void PreThread(ThreadTree &T, ThreadNode *pre)
{
    if (T != nullptr) {
        Tvisit(T, pre);
        if (T->ltag == 0)   // 防止lchild回到前驱节点
            PreThread(T->lchild, pre);
        PreThread(T->rchild, pre);
    }
}

void CreatePreThread(ThreadTree &T)
{
    ThreadNode *pre = nullptr;
    
    if (T != nullptr) {
        PreThread(T, pre);
        if (pre->rchild == nullptr)
            pre->rtag = 1;
    }
}

// *** 后序线索化 ***
void PostThread(ThreadTree &T, ThreadNode *pre)
{
    if (T != nullptr) {
        PostThread(T->lchild, pre);
        PostThread(T->rchild, pre);
        Tvisit(T, pre);
    }
}

void CreatePostThread(ThreadTree &T)
{
    ThreadNode *pre = nullptr;
    if (T != nullptr) {
        PostThread(T, pre);
        if (pre->rchild == nullptr)
            pre->rtag = 1;
    }
}

// *** 中序后继结点 ***
ThreadNode* FirstNode(ThreadNode *p)
{
    while (p->ltag == 0) p = p->lchild;
    return p;
}

ThreadNode* InThreadNext(ThreadNode *p)
{
    if (p->rtag == 0)
        return FirstNode(p->rchild);
    else
        return p->rchild;
}

// *** 中序前驱节点 ***
ThreadNode* LastNode(ThreadNode *p)
{
    while (p->rtag == 0) p = p->rchild;
    return p;
}

ThreadNode* InThreadPrev(ThreadNode *p)
{
    if (p->ltag == 1) return p->lchild;
    else return LastNode(p->lchild);
}

// *** 线索中序遍历 ***
void InThreadOrder(ThreadTree T)
{
    for (ThreadNode *p = T; p != nullptr; p = InThreadNext(p)) {
        printf("%d\n", p->data);
    }
}

// *** 逆向中序遍历 ***
void RevInThreadOrder(ThreadTree T)
{
    for (ThreadNode *p = LastNode(T); p != nullptr; p = InThreadPrev(p)) {
        printf("%d\n", p->data);
    }
}

// *** 先序后继节点 ***
ThreadNode* PreThreadNext(ThreadNode *p)
{
    if (p->ltag == 0) return p->lchild;
    else return p->rchild;
}

// ** 先序前驱节点 ***
ThreadNode* PreThreadPrev(ThreadNode *p)
{
    if (p->ltag == 1) return p->lchild;
    return nullptr;
    // p往左右孩子找是找不到前驱的，假设树为三叉链表，即存在指向父结点的指针，尝试找到p的前驱节点
    // 1. 如果p是父结点的左孩子，则p的父结点就是p的前驱结点
    // 2. 如果p是父结点的右孩子，且父结点没有左子树，则p的父结点就是p的前驱结点
    // 3. 如果p是父结点的右孩子，找左孩子的最后一个结点
}

// *** 后序前驱节点 ***
ThreadNode* LastThreadPrev(ThreadNode *p)
{
    if (p->ltag == 1) return p->lchild; // 没有左孩子
    if (p->rtag == 0) return p->rchild; // 有左孩子，有右孩子
    else return p->lchild; // 有左孩子，没有右孩子
}

// *** 后序后继结点 ***
ThreadNode* LastThreadNext(ThreadNode *p)
{
    if (p->rtag == 1) return p->rchild;
    return nullptr;
    // p左右孩子都是找不到后继结点的，所以假设为三叉链表，有指向父结点的指针
    // 1. p是父结点的右孩子，则父结点就是p的后继结点
    // 2. p是父结点的左孩子，且父结点右孩子为空，则父结点就是p的后继结点
    // 3. p是父结点的左孩子，且父结点右孩子非空，找到右孩子第一个结点
}

// ** 查找 **
BSTNode* BST_Search(BSTree T, int key)
{
    BSTNode *p = T; // 工作指针
    while (p != nullptr && p->data != key) {
        if (p->data > key) p = p->lchild;
        else p = p->rchild;
    }
    return p;
}

// ** 插入 **
bool BST_Insert(BSTree &T, int key)
{
    BSTNode *p = T, *pre = nullptr; // 工作指针
    while (p != nullptr && p->data != key) { // 查找key
        pre = p;
        if (p->data > key) p = p->lchild;
        else p = p->rchild;
    }
    if (p != nullptr)
        return false; // 不能存在相同的值
    p = (BSTNode*)malloc(sizeof(BSTNode)); // 插入
    p->lchild = nullptr;
    p->rchild = nullptr;
    p->data = key;
    if (pre == nullptr) {
        T = p;
    } else {
        if (pre->data > key) pre->lchild = p;
        else pre->rchild = p;
    }
    return true;
}

// ** 构造BST **
bool BST_Create(BSTree &T, int arr[], int n)
{
    T = nullptr;
    for (int i = 0; i < n; i++)
        BST_Insert(T, arr[i]);
    return true;
}
